package datastructure.hashTable;

import datastructure.find.SequentialSearchST;

/**
 * @author MaoLin Wang
 * @description 哈希表
 * @date 2020/8/27 10:09 上午
 */
public class SeparateChainingHashST<Key, Value> {

    private int N;
    private int M;

    private SequentialSearchST<Key, Value>[] st;

    public SeparateChainingHashST(int m) {
        M = m;
        this.st=new SequentialSearchST[M];
        for (int i = 0; i < M; i++) {
            st[i]=new SequentialSearchST<>();
        }
    }

    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff)%M;
    }

    public Value get(Key key){
        if (key==null){
            return null;
        }
        int hash = hash(key);
        return st[hash].get(key);
    }

    public void put(Key key,Value value){
        if (key==null){
            return ;
        }
        if (value==null){
            delete(key);
        }
        if (N >= M*8){
            resize(M*2);
        }
        st[hash(key)].put(key,value);
        N++;
    }

    private void resize(int size) {
        SeparateChainingHashST<Key,Value>newSt=new SeparateChainingHashST<>(size);
        for (int i = 0; i < M; i++) {
            for (Key key : st[i].keys()) {
                if (key!=null){
                    newSt.put(key,get(key));
                }
            }
        }
        this.M=newSt.M;
        this.N=newSt.N;
        this.st=newSt.st;

    }

    private void delete(Key key) {
        if (key==null){
            return;
        }
        if (contains(key)){
            N--;
            st[hash(key)].delete(key);
            if (N>0 && N<=M*2){
                resize(M/2);
            }
        }
    }

    private boolean contains(Key key) {
        return get(key)!=null;
    }


    public static void main(String[] args) {
        SeparateChainingHashST<String,String>st=new SeparateChainingHashST<>(3);
        st.put("1","wml1");
        st.put("2","wml2");
        st.put("54","hah");
        System.out.println(st.M);
        st.put("214","41");
        System.out.println(st.M);
        System.out.println(st.get("214"));
        st.delete("2");
        System.out.println(st.get("2"));
        System.out.println(st.M);
    }
}
